package DataStrue;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
        static class TreeNode {
            public char val;
            public TreeNode left;
            public TreeNode right;

            public TreeNode(char val) {
                this.val = val;
            }

        }

        private TreeNode root; //指向根节点

        public TreeNode createTree() {
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            E.right = H;
            return A;
        }


        public void preOrder(TreeNode root) {
            if (root == null) {
                return ;
            }
            // List<TreeNode> list = root;
            System.out.println(root.val + " ");
            preOrder(root.left);
            preOrder(root.right);

        }

        public void middleOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            middleOrder(root.left);
            System.out.println(root.val + " ");
            middleOrder(root.right);

        }


        public void postOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.println(root.val + " ");
        }

        //在树中找到一个节点。根据前序遍历的方式进行查找
        public boolean isOperation(TreeNode root, int key) {
            if (root == null) {
                return false;
            }

            if (root.val == key) {
                return true;
            }

            boolean leftKey = isOperation(root.left, key);
            if (leftKey == true) {
                return true;
            }

            boolean rightKey = isOperation(root.right, key);
            if (rightKey == true) {
                return true;
            }
            return false;
        }


        public int leafSize = 0;

        //计算叶子结点
        public void getDeafSize(TreeNode root) {
            if(root == null){
                return;
            }

            if(root.left == null && root.right == null){
                leafSize++;
            }

            getDeafSize(root.left);
            getDeafSize(root.right);


        }


        public int getDDeafSize(TreeNode root) {
            if(root == null){
                return 0;
            }
            if(root.left == null && root.right == null){
                return 1;
            }
            return getDDeafSize(root.left)+ getDDeafSize(root.right);
        }


        public int getKLevel(TreeNode root, int k) {
            if(root == null){
                return 0;
            }
            if(k == 1){
                return 1;
            }
            return getKLevel(root.left, k -1) + getKLevel(root.right , k -1);

        }









        public int getHeight(TreeNode root){
            if(root == null){
                return 0;
            }
            int leftHeight =  getHeight(root.left);
            int rightHeight = getHeight(root.right);
            if(leftHeight >= 0 && rightHeight >= 0
                    && Math.abs(leftHeight-rightHeight) <= 1){
                return Math.max(leftHeight,rightHeight) + 1;
            }else{
                return -1;
            }
        }
    //判断这个二叉树是否是完全二叉树
    public static boolean isComplete(TreeNode root){
            if(root == null){
                return true;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode cur = queue.poll();
                if(cur != null){
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }else{
                    break;
                }

            }
            while(!queue.isEmpty()){
                TreeNode cur = queue.poll();
                if(cur != null){
                    return false;
                }

            }
            return true;
    }

}
